package leetcode.D500.T417;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution {
    private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {-1, 1, 0, 0};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> result = new LinkedList<>();
        int m = heights.length, n = heights[0].length;
        boolean[][] can1 = new boolean[m][n];
        boolean[][] can2 = new boolean[m][n];
        for(int i=0; i<n; ++i) {
            dfs(heights, 0, i, can1);
            dfs(heights, m-1, i, can2);
        }
        for(int i=0; i<m; ++i) {
            dfs(heights, i, 0, can1);
            dfs(heights, i, n-1, can2);
        }
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(can1[i][j] && can2[i][j]) {
                    List<Integer> temp = new ArrayList<>(2);
                    temp.add(i);
                    temp.add(j);
                    result.add(temp);
                }
            }
        }
        return result;
    }
    private void dfs(int[][] heights, int x, int y, boolean[][] can) {
        if(can[x][y]) {
            return;
        }
        can[x][y] = true;
        int m = heights.length, n = heights[0].length;
        for(int i=0; i<4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx >= m || ny < 0 || ny >= n || heights[nx][ny] < heights[x][y]) {
                continue;
            }
            dfs(heights, nx, ny, can);
        }
    }
}